/**
 * Binary Search 二分查找
 * https://leetcode-cn.com/problems/binary-search/
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  // 极限条件，返回-1
  if (!nums || !nums.length) {
    return -1;
  }
  // 如果首或尾刚好是，则返回
  let len = nums.length;

  // 头是则直接返回
  if (nums[0] === target) {
    return 0;
  }

  // 尾是则直接返回
  if (nums[len - 1] === target) {
    return len - 1;
  }

  // 如果长度少于2说明未找到，返回-1
  if (len <= 2) {
    return -1;
  }

  //从中间开始，二分查找
  let i = Math.ceil(len / 2) - 1;

  //声明一个变量，避免死循环
  let d = 0;

  while (i >= 1 && i < len - 1) {
    //找到则返回
    if (nums[i] === target) {
      return i;
    }
    // 如果当前数比目标函数大，则左移
    if (nums[i] > target) {
      if (!d) {
        // 初始化赋值
        d = -1;
      } else if (d > 0) {
        //一开始向左，现在向右，表明没有，返回-1
        return -1;
      }
      i--;
    } else {
      if (!d) {
        // 初始化赋值
        d = 1;
      } else if (d < 0) {
        //一开始向右，现在向左，表明没有，返回-1
        return -1;
      }
      i++;
    }
  }
  return -1;
};

let rslt = search([-1, 0, 3, 5, 9, 12], 2);

console.log(rslt);

//================v1要点总结===============
/**
 * 1. 注释先行，理清思路（居然i--都写成了i++）
 * 2. 反复横跳出现死循环
 * 3. 起始index，当长度为3时，出现错误
 * 4. 内存占用较大
 * 5. 这一版就没有用二分查找，只在一开始分割了一次，后来就是简单的遍历！！！！！！！！！！！！！！好久没做了，菜
 */
